#ifndef ALGO_H_
#define ALGO_H_

#include <cstdint>
#include <string>

namespace
{
constexpr int MAX = ~(1 << 31);

inline int apples(int rest)
{
    if (rest < 0) return MAX;
    if (rest == 0) {
        return 0;
    }

    int p1 = apples(rest - 8);
    int p2 = apples(rest - 6);
    p1 += p1 == MAX ? 0 : 1;
    p2 += p2 == MAX ? 0 : 1;
    return p1 < p2 ? p1 : p2;
}

inline char eat_grass(char who, int rest)
{
    char enemy = who == 'A' ? 'B' : 'A';
    if (rest == 0) {
        return enemy;
    }

    for (int k = 1; k <= rest; k *= 4) {
        if (eat_grass(enemy, rest - k) == who) return who;
    }
    return enemy;
}

inline bool is_good(std::string& path, int l, int r)
{
    while (l < r) {
        if (path[l++] != path[r--]) return false;
    }
    return true;
}

inline int good(std::string& path, int i)
{
    if (i == path.size()) {
        int cnt = 0;
        for (int l = 0; l < path.size(); l++) {
            for (int r = l + 1; r < path.size(); r++) {
                if (is_good(path, l, r)) cnt++;
                if (cnt > 1) return 0;
            }
        }
        return cnt == 1 ? 1 : 0;
    }
    else {
        // i在正常位置
        int ans = 0;
        path[i] = 'r';
        ans += good(path, i + 1);
        path[i] = 'e';
        ans += good(path, i + 1);
        path[i] = 'd';
        ans += good(path, i + 1);
        return ans;
    }
}
}   // namespace

// 暴力方法
namespace burte
{
inline int bags1(int apple)
{
    int ans = apples(apple);
    return ans == MAX ? 0 : ans;
}

inline char win(int n)
{
    return eat_grass('A', n);
}

inline bool is(int n)
{
    for (int i = 1; i < n; i++) {
        int k = i, a = i;
        while (k < n) {
            k += ++a;
        }
        if (k == n) return true;
    }
    return false;
}

inline int good_string(int n)
{
    std::string path(n, ' ');
    return good(path, 0);
}
}   // namespace burte

// 规律求解
namespace lxj
{
// 有装下8个苹果的袋子、装下6个苹果的袋子，一定要保证买苹果时所有使用的袋子都装满
// 对于无法装满所有袋子的方案不予考虑，给定n个苹果，返回至少要多少个袋子
// 如果不存在每个袋子都装满的方案返回-1
inline int bags1(int apple)
{
    if (apple % 2 != 0) return 0;
    if (apple == 6 || apple == 8) return 1;
    if (apple == 12 || apple == 14 || apple == 16) return 2;
    return (apple - 18) / 8 + 3;
}

// 草一共有n的重量，两只牛轮流吃草，A牛先吃，B牛后吃
// 每只牛在自己的回合，吃草的重量必须是4的幂，1、4、16、64....
// 谁在自己的回合正好把草吃完谁赢，根据输入的n，返回谁赢
inline char win(int n)
{
    int ans = n % 5;
    return ans == 0 || ans == 2 ? 'B' : 'A';
}

// 判断一个数字是否是若干数量(数量>1)的连续正整数的和
inline bool is(int n)
{
    return (n & (n - 1)) != 0;
}

// 可以用r、e、d三种字符拼接字符串，如果拼出来的字符串中
// 有且仅有1个长度>=2的回文子串，那么这个字符串定义为"好串"
// 返回长度为n的所有可能的字符串中，好串有多少个
// 结果对 1000000007 取模， 1 <= n <= 10^9
// 示例：
// n = 1, 输出0
// n = 2, 输出3
// n = 3, 输出18
inline int good_string(int n)
{
    if (n <= 1) return 0;
    if (n == 2) return 3;
    if (n == 3) return 18;
    return (int)((int64_t)6 * (n + 1)) % 1000000007;
}
}   // namespace lxj

#endif